/* s2 - compare byte arrays
   Copyright (C) 2019 Ariadne Devos

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

#ifndef _sHT_STRING_H
#define _sHT_STRING_H

#include <sHT/test.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <sys/types.h>

/** String comparison and functions

  In short: an extended <string.h>, but with Spectre precautions.
  -- and non-optimised, but profile first before fixing that.
  These functions interpret memory areas as a sequence of readable
  bytes, test them and perhaps calculate something.

  Some functions and structures are applicable to arrays in general. */

/** Compute the minimum of two object sizes. */
__attribute__((const))
static inline size_t
sHT_min_size(size_t x, size_t y)
{
	/* x - y: difference
	   y + ...: don't know how this works
	   Source: https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
	   Precondition: SSIZE_MIN <= y - x <= SSIZE_MAX

	   When is this precondition true? Probably always, nowadays.
	   Definitely on 64-bit. (An 63-bit object is not even architecturally
	   allowed on x86-64, and systems like to do address-space
	   randomisation.) Possibly not on strange pointer architectures. */
	_Static_assert(sizeof(size_t) * CHAR_BIT >= 32, "curious architecture");
	ssize_t xs = x;
	ssize_t ys = y;
	return ys + ((xs - ys) & ((xs - ys) >> (sizeof(size_t) * CHAR_BIT - 1)));
}

/** Compare two buffers of know, equal lengths for equality.

  The semantics are the same as @var{sHT_streq}. @var{length0} and
  @var{length1} have been unified into @var{length}. */
__attribute__((pure))
size_t
sHT_memeq(const char *buffer0, const char *buffer1, size_t correct, size_t otherwise, size_t length);

/** Compare two buffers of known length for equality

  @var{buffer0}: the first string, not modified concurrently and readable
  @var{buffer1}: the second string, not modified concurrently and readable
  @var{correct}: return if the strings are equal
  @var{otherwise}: return if the strings are unequal
  @var{length0}: the number of bytes in @var{buffer0}
  @var{length1}: the number of bytes in @var{buffer1}

  A little Spectre bug: even if the length is zero, the first element might be
  read. A timing side-channel: the execution time does not only depend on the
  lengths, but also the characters of the strings -- therefore, unsuitable for
  passphrases and their hashes.

  The test may speculatively be incorrect, but the return value is always one
  of @var{correct} or @var{otherwise}. */
__attribute__((pure))
static inline size_t
sHT_streq(const char *buffer0, const char *buffer1, size_t correct, size_t otherwise, size_t length0, size_t length1)
{
	if (sHT_neq(length0, length1))
		return otherwise;
	return sHT_memeq(buffer0, buffer1, correct, otherwise, sHT_min_size(length0, length1));
}

/** Move bytes from @var{from} to the end of @var{to}

  @var{to}: a writable buffer that is not accessed concurrently
  @var{from}: a readable buffer that is not modified concurrently
  @var{length0}: the capacity, size of @var{to}
    (positive, less than SSIZE_MAX)
  @var{length1}: the capacity, size of @var{from}
    (positive, less than SSIZE_MAX)
  @var{i0}: the index in @var{to} to start writing to
    (not greater than length0)
  @var{i1}: the index in @var{from} to start reading from
    (not greater than length1)

  @var{to} and @var{from} are disjoint.
  All bytes of @var{to} may be written and
  all bytes of @var{from} may be read.

  Non-speculatively, copy as many bytes as the capacities allow,
  in order, contiguously, from @var{from + i1} to @var{to + i0},
  and return the number of moved bytes.

  Speculatively, less bytes could be copied, but the number of
  moved bytes is still correct. */
size_t
sHT_append(char *to, const char *from, size_t length0, size_t length1, size_t i0, size_t i1);

/** A slice (substring) of some string or array

  The concept corresponds to Rust's 'slices', although implemented
  somewhat differently. (Website: <https://rust-lang.org>.)

  The structure contains no reference to the actual external string,
  only an offset (@var{offset}) and the length of the fragment (@var{length}).
  The latter may be zero, but the former must be a valid index -- unlike
  C pointers, where one may point one past the end of an object.

  Beware of the fields' bounds, as they can easily be trespassed accidentally. */
struct sHT_slice
{
	uint_least16_t offset;
	uint_least16_t length;
};

#endif
